package p3.structures;

import java.util.Random;

import p3.structures.TreeNode.Alphabet;


public class Tree {
	protected Tree[] childs;
	protected Tree parent;
	protected TreeNode node;
	int numChilds;
	int depth;
	
	public Tree(){
		childs = null;
		parent = null;
		depth = 0;
		node = new TreeNode();
	}
	
	public void setChilds(Tree... childs){
		numChilds = childs.length;
		this.childs = new Tree[numChilds];
		for (int i=0;i<numChilds;i++){
			this.childs[i] = childs[i];
			this.childs[i].setDepth(depth+1);
			this.childs[i].setParent(this);
		}
	}
	
	
	public void generateChilds(int type, int max_depth){
		switch(type){
		case 0: generateChilds_full(0, max_depth); break;
		case 1: generateChilds_grow(0, max_depth); break;
		}
	}
	
	private void generateChilds_full(int depth, int max_depth){
		if (depth < max_depth) {
			node.setRandomFunction();
			numChilds = node.getArity();
			if (numChilds > 0){
				childs = new Tree[numChilds];
				for (int i=0;i<numChilds;i++){
					childs[i] = new Tree();
					childs[i].setParent(this);
					childs[i].setDepth(depth+1);
					childs[i].generateChilds_full(depth+1, max_depth);
				}
			}
		} else {
			node.setRandomTerminal();
		}
	}
	
	private void generateChilds_grow(int depth, int max_depth){
		if (depth < max_depth) {
			node.setRandom();
			numChilds = node.getArity();
			if (numChilds > 0){
				childs = new Tree[numChilds];
				for (int i=0;i<numChilds;i++){
					childs[i] = new Tree();
					childs[i].setParent(this);
					childs[i].setDepth(depth+1);
					childs[i].generateChilds_grow(depth+1, max_depth);
				}
			}
		} else {
			node.setRandomTerminal();
		}
	}
	
	public Tree getRandomNode(){
		Random r = new Random();
		if (depth != 0 && r.nextFloat() < 0.8) return this;
		else {
			Tree child = getRandomChild();
			if (child == null) return this;
			else return child.getRandomNode();
		}
	}
	
	public Tree getRandomChild(){
		Random r = new Random();
		if (numChilds > 0){
			int pos = r.nextInt(numChilds);
			return childs[pos];
		}
		return null;
	}
	
	public boolean replace(Tree child, Tree newChild){
		boolean ret = false;
		for (int i=0;i<childs.length;i++){
			if (child == childs[i]){
				childs[i] = newChild;
				newChild.setParent(this);
				newChild.setDepth(depth+1);
				newChild.refreshDepth();
				ret = true;
			}
		}
		return ret;
	}
	
	public boolean isLeaf(){ return numChilds == 0; }
	public Tree getParent(){ return parent; }
	public int getNumChild() {return numChilds;}

	public Tree getChild(int i){ if (i<numChilds) return childs[i]; else return null;}

	public TreeNode getNode() { return node;}

	public Alphabet getTerm(){ return node.getTerm(); }
	public Tree getCopy() {
		Tree ret = new Tree();
		
		ret.setDepth(depth);
		ret.setNode(node.getCopy());
		
		Tree[] ret_childs = new Tree[numChilds];
		for (int i=0;i<numChilds;i++){
			ret_childs[i] = childs[i].getCopy();
		}
		ret.setChilds(ret_childs);
		
		return ret;
	}

	public int getMaxDepth(){
		int depth, tmp;
		
		if (isLeaf()) depth = 0;
		else{
			depth = childs[0].getMaxDepth() + 1;
			for (int i=1;i<numChilds;i++){
				tmp = childs[i].getMaxDepth() + 1;
				if (tmp > depth) depth = tmp;
			}
		}
		
		return depth;
	}

	private void setParent(Tree parent){ this.parent = parent; }	
	public void setDepth(int depth){ this.depth = depth; }
	private void setNode(TreeNode node) { this.node = node.getCopy(); }

	public void refreshDepth() {
		if (isLeaf()) return;
		
		for (int i=0;i<numChilds;i++){
			childs[i].setDepth(depth+1);
			childs[i].refreshDepth();
		}
		
	}

	public static void main(String[] args){
		Tree tree = new Tree();
		tree.generateChilds(1, 4);
		System.out.println(tree);
	}

	public String toString() {
		
		
		String s = "";
		for (int i=0;i<depth;i++) s += " ";
		s += node.toString() + "\n";
		if (numChilds > 0) for (int i=0;i<numChilds;i++) s += childs[i].toString();
		
		/*
		 if (numChilds > 0){
			s += " ( ";
			for (int i=0;i<numChilds-1;i++) s += childs[i].toString() + " , ";
			s += childs[numChilds-1].toString();
			s += " ) ";
		 }
		*/
		return s;
	}

	
}
